ConstraintChecker

function

ConstraintChecker()

Option name	Type	Description
flowviz	FlowViz	A reference to the FlowViz object

function ConstraintChecker(flowviz) {
    fv = flowviz;
}

IsValidEdge

method

ConstraintChecker.prototype.IsValidEdge()

Option name	Type	Description
from	FlowNode	The starting node of an edge
to	FlowNode	The ending node of an edge
edges	object	The list of edges in the graph

ConstraintChecker.prototype.IsValidEdge = function(from, to, edges) {
    var fromConstraints = from.type.GetConstraintObject();
    var toConstraints = to.type.GetConstraintObject();

    // Collect all nodes are connected to "from" or "to".
    var fromNeighbors = [];
    var toNeighbors = [];

    _.forEach(edges, function (edge) {
        if (edge.start === from) {
            fromNeighbors.push(edge.end);
        }
        if (edge.end === to) {
            toNeighbors.push(edge.start);
        }
        // We don't check if edge from "from" to "to" already exists, that is done elsewhere.
    });

    var msg = "";

    // Check that number of edges from "from" is not at maximum yet.
    if (fromNeighbors.length >= fromConstraints.outgoing.range[1]) {
        msg = 'The start node already has maximum number of outgoing edges.';
        fv.ShowWarning(msg);
        console.error(msg);
        return false;
    }
    // Check that number of edges to "to" is not at maximum yet.
    if (toNeighbors.length >= toConstraints.incoming.range[1]) {
        msg = 'The end node already has maximum number of incoming edges.';
        fv.ShowWarning(msg);
        console.error(msg);
        return false;
    }
    // Check that "to" type is an allowable type for "from"
    // and that "from" hasn't exceeded the limit of neighbors of type "to".
    if (!CheckTypes(to.type, fromConstraints.outgoing.types, fromNeighbors)) {
        msg = 'The end node is an invalid outgoing node for the start node ' +
            'or the maximum number of edges of this type is exceeded.';
        fv.ShowWarning(msg);
        console.error(msg);
        return false;
    }
    // Check that "from" type is an allowable type for "to"
    // and that "to" hasn't exceeded the limit of neighbors of type "from".
    if (!CheckTypes(from.type, toConstraints.incoming.types, toNeighbors)) {
        msg = 'The start node is an invalid incoming node for the end node.' +
            'or the maximum number of edges of this type is exceeded.';
        fv.ShowWarning(msg);
        console.error(msg);
        return false;
    }
    return true;
};

IsValidGraph

method

ConstraintChecker.prototype.IsValidGraph() ->bool

Option name	Type	Description
nodes	object	The list of nodes in the graph
edges	object	The list of edges in the graph

ConstraintChecker.prototype.IsValidGraph = function(nodes, edges) {
    var incomingEdges = {};
    var outgoingEdges = {};
    _.forEach(edges, function(edge) {
        incomingEdges[edge.end] = edge;
        outgoingEdges[edge.start] = edge;
    });
    var msg = "";
    var that = this;
    _.forEach(nodes, function(node) {
        var constraints = node.type.GetConstraintObject();
        var incoming = node in incomingEdges ? incomingEdges[node] : [];
        var outgoing = node in outgoingEdges ? outgoingEdges[node] : [];
        if (incoming.length < constraints.incoming.range[0]) {
            msg = 'Node of type ' + node.type.name + ' has too few incoming edges.';
            fv.ShowWarning(msg);
            console.error(msg);
            return false;
        } else if (incoming.length > constraints.incoming.range[1]) {
            msg = 'Node of type ' + node.type.name + ' has too many incoming edges.';
            fv.ShowWarning(msg);
            console.error(msg);
            return false;
        }
        if (outgoing.length < constraints.outgoing.range[0]) {
            msg = 'Node of type ' + node.type.name + ' has too few outgoing edges.';
            fv.ShowWarning(msg);
            console.error(msg);
            return false;
        } else if (incoming.length > constraints.outgoing.range[1]) {
            msg = 'Node of type ' + node.type.name + ' has too many outgoing edges.';
            fv.ShowWarning(msg);
            console.error(msg);
            return false;
        }
        if (that.GetRequiredTypes(node, edges, true).length > 0) {
            msg = 'Node of type ' + node.type.name + ' is missing required outgoing edges.';
            fv.ShowWarning(msg);
            console.error(msg);
            return false;
        } else if (that.GetRequiredTypes(node, edges, false).length > 0) {
            msg = 'Node of type ' + node.type.name + ' is missing required incoming edges.';
            fv.ShowWarning(msg);
            console.error(msg);
            return false;
        }
    });
    // The previous "returns" only return from the forEach loop.
    // If the error message is set, graph is not valid.
    if (msg !== "") {
        return false;
    }
    // Run the graph through the validators defined by the user.
    for (var validator in fv.App.Callbacks.GraphValidators) {
        if (fv.App.Callbacks.GraphValidators.hasOwnProperty(validator)) {
            if (!fv.App.Callbacks.GraphValidators[validator](nodes, edges)) {
                return false;
            }
        }
    }
    return true;
};

GetRequiredTypes

method

ConstraintChecker.prototype.GetRequiredTypes() ->object

Option name	Type	Description
node	FlowNode	The node for which to get the types
edges	object	The list of edges in the graph
isOutgoing	bool	If true, return outgoing types, otherwise return incoming.

ConstraintChecker.prototype.GetRequiredTypes = function(node, edges, isOutgoing) {
    return GetMissingTypes(node, edges, isOutgoing, true);
};

GetPossibleTypes

method

ConstraintChecker.prototype.GetPossibleTypes() ->object

Option name	Type	Description
node	FlowNode	The node for which to get the types
edges	object	The list of edges in the graph
isOutgoing	bool	If true, return outgoing types, otherwise return incoming.

ConstraintChecker.prototype.GetPossibleTypes = function(node, edges, isOutgoing) {
    return GetMissingTypes(node, edges, isOutgoing, false);
};

GetUnambiguousRequiredTypes

method

ConstraintChecker.prototype.GetUnambiguousRequiredTypes() ->object

Option name	Type	Description
node	FlowNode	The node for which to get the types
edges	object	The list of edges in the graph
isOutgoing	bool	If true, return outgoing types, otherwise return incoming.

ConstraintChecker.prototype.GetUnambiguousRequiredTypes = function(node, edges, isOutgoing) {
    var constraints = isOutgoing ? node.type.GetConstraintObject().outgoing : node.type.GetConstraintObject().incoming;
    var neighbors = [];
    var neighborCountByTypeName = {};

    _.forEach(edges, function (edge) {
        if (edge.start === node && isOutgoing) {
            neighbors.push(edge.end);
            if (!(edge.end.type.type in neighborCountByTypeName)) {
                neighborCountByTypeName[edge.end.type.type] = 0;
            }
            neighborCountByTypeName[edge.end.type.type] += 1;
        }
        if (edge.end === node && !isOutgoing) {
            neighbors.push(edge.start);
            if (!(edge.start.type.type in neighborCountByTypeName)) {
                neighborCountByTypeName[edge.start.type.type] = 0;
            }
            neighborCountByTypeName[edge.start.type.type] += 1;
        }
    });

    // Check if node already has max number of neighbors.
    if (neighbors.length >= constraints.range[1]) {
        return [];
    }

    var typeNameToType = {};
    _.forEach(fv.Config.getAllNodeTypes(), function(t) {
        typeNameToType[t.type] = t;
    });
    var possibleTypes = [];
    var typesObject = constraints.types;
    for (var type in typesObject) {
        if (typesObject.hasOwnProperty(type)) {
            var index = type.indexOf("*");
            if (index == -1) {
                // Leaf type
                if (!(type in neighborCountByTypeName) || neighborCountByTypeName[type] < typesObject[type][1]) {
                    if ( (type in neighborCountByTypeName && neighborCountByTypeName[type] < typesObject[type][0])
                        || (!(type in neighborCountByTypeName) && typesObject[type][0] > 0)
                        || (neighbors.length < constraints.range[0] && typesObject.length == 1)) {
                        possibleTypes.push(typeNameToType[type]);
                    }
                }
            }
        }
    }
    // Now possibleTypes contains NodeTypes that must be neighbors to our node.
    // But we still need to check if those NodeTypes are permitted by their constraints to be connected to our node.
    return GetValidBothWayNeighbors(node.type, possibleTypes, isOutgoing);
};

CheckTypes

function

CheckTypes() ->boolean

Option name	Type	Description
typeToCheck	NodeType	NodeType to verify
typesObject	object	Types object specified in the constraints section of the config JSON object
neighbors	Array	List of current neighbors for the current node

function CheckTypes(typeToCheck, typesObject, neighbors) {
    for (var type in typesObject) {
        if (typesObject.hasOwnProperty(type)) {
            if (type === "*") {
                // Any type is allowed
                return true;
            }
            if (type === typeToCheck.type) {
                var count = 0;
                // Check that maximum number of edges for this type is not exceeded.
                _.forEach(neighbors, function(node) {
                    if (node.type.type === type) {
                        count += 1;
                    }
                });
                return count < typesObject[type][1];
            }
            var index = type.indexOf("*");
            if (index > -1) {
                // This is not a leaf type.
                var actualType = type.slice(0, index-1);
                var parent = typeToCheck.GetParent();
                while (parent != null) {
                    if (parent.type === actualType) {
                        count = 0;
                        _.forEach(neighbors, function(node) {
                            parent = node.type.GetParent();
                            while (parent != null) {
                                if (parent.type === actualType) {
                                    count += 1;
                                    break;
                                }
                                parent = parent.GetParent();
                            }
                        });
                        return count < typesObject[type][1];
                    }
                    parent = parent.GetParent();
                }
            }
        }
    }
    return false;
}

GetMissingTypes

function

GetMissingTypes() ->object

Option name	Type	Description
node	FlowNode	The node for which to get the types
edges	object	The list of edges in the graph
isOutgoing	bool	If true, return outgoing types, otherwise return incoming.
isRequired	bool	If true, return required types, otherwise return possible.

function GetMissingTypes(node, edges, isOutgoing, isRequired) {
    var constraints = isOutgoing ? node.type.GetConstraintObject().outgoing : node.type.GetConstraintObject().incoming;
    var neighbors = [];
    var neighborCountByTypeName = {};

    _.forEach(edges, function (edge) {
        if (edge.start === node && isOutgoing) {
            neighbors.push(edge.end);
            if (!(edge.end.type.type in neighborCountByTypeName)) {
                neighborCountByTypeName[edge.end.type.type] = 0;
            }
            neighborCountByTypeName[edge.end.type.type] += 1;
        }
        if (edge.end === node && !isOutgoing) {
            neighbors.push(edge.start);
            if (!(edge.start.type.type in neighborCountByTypeName)) {
                neighborCountByTypeName[edge.start.type.type] = 0;
            }
            neighborCountByTypeName[edge.start.type.type] += 1;
        }
    });

    // Check if node already has max number of neighbors.
    if (neighbors.length >= constraints.range[1]) {
        return [];
    }

    var typeNameToType = {};
    _.forEach(fv.Config.getAllNodeTypes(), function(t) {
        typeNameToType[t.type] = t;
    });
    var possibleTypes = [];
    var typesObject = constraints.types;
    for (var type in typesObject) {
        if (typesObject.hasOwnProperty(type)) {
            if (type === "*") {
                // Any type is allowed
                if (neighbors.length < typesObject[type][1]) {
                    if (!isRequired ||
                        (isRequired && neighbors.length < Math.max(constraints.range[0], typesObject[type][0]))) {
                        return GetValidBothWayNeighbors(node, fv.Config.getLeafNodesTypes(), isOutgoing);
                    } else {
                        return [];
                    }
                } else {
                    return [];
                }
            }
            var index = type.indexOf("*");
            if (index > -1) {
                // This is not a leaf type.
                var actualType = typeNameToType[type.slice(0, index - 1)];
                // Get all leaves that correspond to this parent type.
                var childLeaves = [];
                function getChildLeaves(n) {
                    var children = n.GetChildren();
                    if (children == null) {
                        childLeaves.push(n);
                        return;
                    }
                    _.forEach(children, getChildLeaves);
                }
                getChildLeaves(actualType);
                // Sum up all neighbors that are amongst the child leaves
                var count = 0;
                for (var neighborType in neighborCountByTypeName) {
                    if (neighborCountByTypeName.hasOwnProperty(neighborType)) {
                        if (childLeaves.indexOf(typeNameToType[neighborType]) > -1) {
                            count += neighborCountByTypeName[neighborType];
                        }
                    }
                }
                // If max number of edges is not exceeded, any of the child leaves is a possible neighbor
                if (count < typesObject[type][1]) {
                    if (!isRequired) {
                        possibleTypes = possibleTypes.concat(childLeaves);
                    } else {
                        if (count < typesObject[type][0] || neighbors.length < constraints.range[0]) {
                            possibleTypes = possibleTypes.concat(childLeaves);
                        }
                    }
                }
            } else {
                // Leaf type
                if (!(type in neighborCountByTypeName) || neighborCountByTypeName[type] < typesObject[type][1]) {
                    if (!isRequired) {
                        possibleTypes.push(typeNameToType[type]);
                    } else {
                        if ( (type in neighborCountByTypeName && neighborCountByTypeName[type] < typesObject[type][0])
                            || (!(type in neighborCountByTypeName) && typesObject[type][0] > 0)
                            || neighbors.length < constraints.range[0]) {
                            possibleTypes.push(typeNameToType[type]);
                        }
                    }
                }
            }
        }
    }
    // Now possibleTypes contains NodeTypes that could be neighbors to our node.
    // But we still need to check if those NodeTypes are permitted by their constraints to be connected to our node.
    return GetValidBothWayNeighbors(node.type, possibleTypes, isOutgoing);
}

GetValidBothWayNeighbors

function

GetValidBothWayNeighbors() ->object

Option name	Type	Description
nodeType	NodeType	The type of the node for which to get the types
neighborTypes	object	The list of possible neighbors' NodeTypes
isOutgoing	bool	If true, neighbors are outgoing relative to the node we're considering, otherwise they're incoming.

function GetValidBothWayNeighbors(nodeType, neighborTypes, isOutgoing) {
    var validNeighbors = [];
    _.forEach(neighborTypes, function(neighbor) {
        var constraints = isOutgoing ? neighbor.GetConstraintObject().incoming : neighbor.GetConstraintObject().outgoing;
        if (CheckTypes(nodeType, constraints.types, [])) {
            validNeighbors.push(neighbor);
        }
    });
    return validNeighbors;
}